Міністерство освіти і науки, молоді та спорту України Національний університет ”Львівська політехніка”
з курсу алгоритми та методи обчислень на тему: «Порозрядне сортування»  Львів - 2012 Зміст Вступ……………………………………………………………3 Сортування……………………………………………………..4 Порозрядне сортування…………………………………...…..7 Алгоритм…………………………………………………….....8 Порозрядне сортування для списків……………………….....9 Порозрядне сортування для масивів…………………..…......10 Ефективність порозрядної сортування……………………....13 Література……………………………………………………....14 Вступ В наш час нові інформаційні технології посідають дуже важливе місце не лише в спеціалізованих, але й в повсякденних сферах життя. Комп’ютери застосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьох інших сферах діяльності людини. Нові інформаційні технології дуже актуальні в наш час і потребують багато уваги для подальшої розробки та вдосконалення. Поряд з цим, велике значення має також і програмування, яке є одним із фундаментальних розділів інформатики і тому не може залишатись осторонь. Програмування містить цілу низку важливих внутрішніх задач. Однією з найбільш важливих таких задач для програмування є задача сортування. Під сортуванням звичайно розуміють перестановки елементів будь-якої послідовності у визначеному порядку. Ця задача є однією з найважливіших тому, що її метою є полегшення подальшої обробки певних даних і, насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку є бінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але його можливо застосовувати лише за умови, що послідовність вже упорядкована, тобто відсортована. Взагалі, відомо, що в будь-якій сфері діяльності, що використовує комп’ютер для запису, обробки та збереження інформації, усі дані зберігаються в базах даних, які також потребують сортування. Певна впорядкованість для них дуже важлива, адже користувачеві набагато легше працювати з даними, що мають певний порядок. Так, можна розташувати всі товари по назві або відомості про співробітників чи студентів за прізвищем або роком народження, тощо. Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв’язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все ефективність за часом та економне використання пам’яті. Метою нашої дослідницької роботи є ознайомлення з методами впорядкування об’єктів, а саме алгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них. Також метою даної курсової роботи є порівняльний аналіз основних методів сортування, використовуваних для обробки даних, вивчення характеристик і особливостей кожного алгоритму сортування. Сортування Сортування (sortіng) − процес, що дозволяє впорядкувати безліч подібних даних у зростаючому або спадаючому порядку. Алгоритми сортування добре досліджені і вивчені. Різні підходи до сортування мають різні характеристики. Хоча деякі методи в середньому можуть бути краще інших, жоден з методів не буде ідеальним для всіх ситуацій, тому кожен програміст повинен мати у своєму розпорядженні кілька різних типів сортування. Сортування застосовується в усіх без винятку областях програмування, будь-то бази даних чи математичні програми. Практично кожен алгоритм сортування можна розбити на три частини: - порівняння, що визначає впорядкованість пари елементів; - перестановку, що змінює місцями пару елементів; - власне сортуючий алгоритм, що здійснює порівняння і перестановку елементів доти, поки всі елементи множини не будуть впорядковані. Подібними властивостями володіють і ті п'ять алгоритмів сортування, що розглянуті нижче. Вони відібрані з безлічі алгоритмів, тому що: по-перше,...